package com.dys.datastructuresandalgorithm.insertsort;

/**
 * @className: com.dys.datastructuresandalgorithm.insertsort.InsertSort
 * @description: 插入排序
 * @author: pine cone
 * @version: v1.0.0
 * @createTime: 2024/05/28 下午11:44
 */
public class InsertSort {

    /**
     * 交换方法：交换一个整型数组中指定下标的两个元素。
     *
     * @param array  需要进行元素交换的整形数组
     * @param first  需要交换的第一个元素的下标。
     * @param second 需要交换的第二个元素的下标。
     */
    public static void swap(int[] array, int first, int second) {
        // 用临时变量存储array数组中第second个元素的值
        int temp = array[second];

        // 将array数组中第second个元素的值更新为第first个元素的值
        array[second] = array[first];

        // 将array数组中第first个元素的值更新为temp变量的值。
        array[first] = temp;
    }

    /**
     * 打印方法：打印整型数组元素
     *
     * @param array 等待打印的整型数组
     */
    public static void printArray(int[] array) {
        for (int j : array) {
            System.out.print(j + " ");
        }
        System.out.println();
    }

    /**
     * 插入排序：对传入的整型数组进行排序-->从小到大
     *
     * @param array 等待传递的整型数组
     */
    public static void insertionSort(int[] array) {
        // 考虑边界情况: 若只有一个元素or没有元素,则不进行排序
        if (array == null || array.length < 2) {
            return;
        }

        // 获取数组长度
        int n = array.length;
        // 0 ~ 0 完成 | 0 ~ 1 | 0 ~ 2 | 0 ~ 3 | 0 ~ n-1
        for (int end = 1; end < n; end++) {
            int newNumberIndex = end;
            // 如果当前所在位置的前一个位置,存在元素,即左边有数值。并且左边的数值比右边的数值大,就需要交换。
            while (newNumberIndex - 1 >= 0 && array[newNumberIndex - 1] > array[newNumberIndex]) {
                // 交换：新插入进来的数值往左移动
                swap(array, newNumberIndex - 1, newNumberIndex);
                // 离开原来的位置,往左移动
                newNumberIndex--;
            }
        }
    }

    /**
     * 插入排序：对传入的整型数组进行排序-->从小到大
     *
     * @param array 等待传递的整型数组
     */
    public static void insertSort(int[] array) {
        // 考虑边界情况: 若只有一个元素or没有元素,则不进行排序
        if (array == null || array.length < 2) {
            return;
        }

        // 获取数组的长度
        int n = array.length;
        // 0 ~ 0 完成 | 0 ~ 1 | 0 ~ 2 | 0 ~ 3 | 0 ~ n-1
        for (int end = 1; end < n; end++) {
            // pre 新元素的前一个位置，前一个位置的元素比后一个位置的元素大，就交换
            for (int pre = end - 1; pre >= 0 && array[pre] > array[pre + 1]; pre--) {
                swap(array, pre, pre + 1);
            }
        }
    }

    public static void main(String[] args) {
        int[] exampleArray = {66, 33, 22, 11, 22, 44, 99};
        System.out.println("********未经过插入排序前的元素******");
        printArray(exampleArray);
        // 执行排序
        // insertionSort(exampleArray);
        insertSort(exampleArray);
        System.out.println("********经过插入排序后的元素******");
        printArray(exampleArray);
    }

}
